#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <assert.h>

namespace xywl {
    // 首先，我们需要一个节点类，带模版的
    template<class T>
    struct list_node 
    {
        T _data;
        list_node<T>* _next;
        list_node<T>* _prev;
        list_node(const T& data = T()) : 
        _data(data), 
        _next(nullptr), 
        _prev(nullptr) 
        {}
    };

    // list的迭代器
    template<class T, class Ref, class Ptr>
    struct list_iterator {
        typedef list_node<T> Node;
        typedef list_iterator<T, Ref, Ptr> Self;
        Node* _node;
        list_iterator(Node* node)
        :_node(node)
        {}
        Ref operator*() {
            return _node->_data;
        }
        Ptr operator->() {
            return &_node->_data;
        }
        Self& operator++() {
            _node = _node->_next;
            return *this;
        }
        Self& operator--() {
            _node = _node->_prev;
            return *this;
        }
        Self& operator++(int) {
            Self temp(*this);
            _node = _node->_next;
            return temp;
        }
        Self& operator--(int) {
            Self temp(*this);
            _node = _node->_prev;
            return temp;
        }
        bool operator!=(const Self& s) const {
            return _node != s._node;
        }
        bool operator==(const Self& s) const {
            return _node == s._node;
        }
    };
    template<class T>
    class list {
            typedef list_node<T> Node;
        public:
            typedef list_iterator<T, T&, T*> iterator;
            typedef list_iterator<T, const T&, const T*> const_iterator;
            iterator begin() {
                return _head->_next;
            }
            iterator end() {
                return _head;
            }
            const_iterator begin() const
            {
                return _head->_next;
            }
            const_iterator end() const 
            {
                return _head;
            }
            void empty_init() {
                _head = new Node;
                _head->_next = _head;
                _head->_prev = _head;
                _size = 0;
            }
            list() {
                empty_init();
            }
            list(std::initializer_list<T> in) {
                empty_init();
                for(auto& s : in) {
                    push_back(s);
                }
            }
            list(const list<T>& t) {
                empty_init();
                for(auto& s : t) {
                    push_back(s);
                }
            }
            list<T>& operator=(list<T> t) {
                swap(t);
                return *this;
            }
            ~list() {
                clear();
                delete _head;
                _head = nullptr;
            }
            void clear() {
                auto it = begin();
                while(it != end()) {
                    it = erase(it);
                }
            }
            void swap(list<T>& t) {
                std::swap(_head, t._head);
                std::swap(_size, t._size);
            }
            void push_back(const T& x) {
                insert(end(), x);
            }
            void push_front(const T& x) {
                insert(begin(), x);
            }
            iterator insert(iterator pos, const T& x) {
                Node* cur = pos._node;
                Node* prev = cur->_prev;
                Node* newnode = new Node(x);
                
                newnode->_next = cur;
                cur->_prev = newnode;
                prev->_next = newnode;
                newnode->_prev = prev;
                ++_size;
                return newnode;
            }
            void pop_back() {
                erase(--end());
            }
            void pop_front() {
                erase(begin());
            }
            iterator erase(iterator pos) {
                assert(pos != end());
                Node* prev = pos._node->_prev;
                Node* next = pos._node->_next;
                next->_prev = prev;
                prev->_next = next;
                delete pos._node;
                _size--;
                return next;
            }
            size_t size() const {
                return _size;
            }
            bool empty() const {
                return _size == 0;
            }
        private:
            Node* _head;
            size_t _size;
    };
}